//邻接矩阵(深度优先遍历)

#pragma once

//图的邻接矩阵存储结构
template <typename V, typename E, int M = 10>
struct AMGraph
{
    V vexs[M];          //顶点
    E arce[M][M];       //邻接矩阵
    int vexnum, arcnum; //顶点和弧的数量
    bool visited[M];    //顶点的访问标志
};

//初始化图 InitGraph(&G)
template <typename V, typename E, int M>
void InitGraph(AMGraph<V, E, M> &G)
{
    G.vexnum = G.arcnum = 0;
    //for(int i=0;i<M;i++)
    //for(int j=0;j<M;j++)
    //G.arce[i][j]=0;
}

//销毁图 DestroyGraph(&G)
template <typename V, typename E, int M>
void DestroyGraph(AMGraph<V, E, M> &G)
{
    G.vexnum = G.arcnum = 0;
}

//添加顶点 AddVertex(&G,vex)
//在图G中插入顶点 vex,若成功则返回新插入顶点的编号
template <typename V, typename E, int M>
int AddVertex(AMGraph<V, E, M> &G, V vex)
{
    if (G.vexnum == M)
        throw "Too many vertexes";

    //插入顶点数据
    int i = G.vexnum;
    G.vexs[i] = vex;
    G.vexnum++; //顶点数增加

    //初始化顶点相连的弧
    for (int j = 0; j < G.vexnum; j++)
    {
        G.arce[i][j] = 0; //邻接矩阵中的第i行
        G.arce[j][i] = 0; //邻接矩阵的第i列
    }

    //返回顶点的编号
    return i;
}

//添加弧（边） AddArc（&G,s,t,e）
//在图G中添加从顶点 s 到顶点 t 的弧及其对应的信息 e
template <typename V, typename E, int M>
void AddArc(AMGraph<V, E, M> &G, int s, int t, E e)
{
    if (s < 0 || s > G.vexnum)
        throw "Invalid s";
    if (t < 0 || t > G.vexnum)
        throw "Invalid t";

    G.arce[s][t] = e;
    G.arcnum++;
}

//从图G中的顶点v 出发深度优先遍历图
//对每个顶点调用 visit() 进行访问
template <typename V, typename E, int M, typename F>
void DFS(AMGraph<V, E, M> &G, int v, F visit)
{
    //访问顶点v
    visit(G.vexs[v]);
    G.visited[v] = true;

    //依次从顶点 v 的未访问的临界点 w 出发深度优先搜索
    for (int w = 0; w < G.vexnum; w++)
        if (G.arce[v][w] && !G.visited[w])
          DFS(G,w,visit);
}

//深度优先搜索图 DFSTraverse(G,visit)
//深度优先遍历图G，对每个顶点调用 visit() 访问
template <typename V, typename E, int M, typename F>
void DFSTraverse(AMGraph<V, E, M> &G, F visit)
{
    //初始化每个顶点的访问标志为为访
    for (int v = 0; v < G.vexnum; v++)
        G.visited[v] = false;
    //从一个为访问的顶点出发进行深度深度优先搜索
    for (int v = 0; v < G.vexnum; v++)
    {
        if (!G.visited[v])
            DFS(G, v, visit);
    }
}